package leetcode.method.dynamic_programming;

public class Program97WordInterleave {

    public Program97WordInterleave() {
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        int s1Length = s1.length();
        int s2Length = s2.length();
        int s3Length = s3.length();
        if (s1Length + s2Length != s3Length) {
            return false;
        }
        boolean[][] dp = new boolean[s1Length + 1][s2Length + 1];
        dp[0][0] = true;
        for (int i = 0; i <= s1Length; i++) {
            for (int j = 0; j <= s2Length; j++) {
                int p = i + j - 1;
                if (i > 0) {
                    dp[i][j] = dp[i][j] || dp[i -1][j] && s1.charAt(i - 1) == s3.charAt(p);
                }
                if (j > 0) {
                    dp[i][j] = dp[i][j] || dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p);
                }
            }
        }
        return dp[s1Length][s2Length];
    }
    public static void main(String[] args) {
        Program97WordInterleave myStack = new Program97WordInterleave();
        System.out.println(myStack.isInterleave("aabcc","dbbca","aadbbcbcac"));
        System.out.println(myStack.isInterleave("aabcc","dbbca","aadbbbaccc"));
        System.out.println(myStack.isInterleave("","",""));
    }
}
